/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package projet2_ro;

import java.util.ArrayList;

/**
 * Class representing all sums we exctracted from the multi-set "multiEnsemble" given in parameter
 * @author Rigon and Houdemer
 */
public class Enumeration {

    int somme; //Valeur de la somme de tous les elements du multiEnsemble
    ArrayList<Integer> multiEnsemble;
    boolean[][] matrice;
    ArrayList<Somme> resultat;

    /**
     * Build the result by creating the Matrix and filling it, and calls "calculer_enumeration" which will fill-in "resultat" with what we want
     * @param multiEnsemble The multi-set from which we want to extract the result
     */
    public Enumeration (ArrayList<Integer> multiEnsemble){
        this.multiEnsemble=multiEnsemble;
        resultat=new ArrayList<Somme>();

        // On calcule la somme des éléments
        for(Integer i : multiEnsemble){
            somme+=i;
        }

         // On crée la matrice de taille somme des éléments du multi ensemble
        matrice = new boolean[somme+1][multiEnsemble.size()];

        // Une somme de 0 en prenant 0 éléments est possible
        for(int i=0; i< multiEnsemble.size(); i++) matrice[0][i] = false; //Premiere colonne a false

        //On remplit la matrice
        for(int i=1; i <= somme; i++){
           boolean trouve=false;
           for(int j=0; j<multiEnsemble.size(); j++){
               int curval=multiEnsemble.get(j);
               if(j==0){
                   if(curval==i) matrice[i][0]=trouve=true;
                   else matrice[i][0]=false;
               }
               else{
                   if(trouve) matrice[i][j]=true;
                   else if(curval==i) matrice[i][j]=trouve=true; //Si j'essaye de faire la somme 'k' avec un element egal a k...
                   else if (curval > i) matrice[i][j] = false;
                   else trouve = matrice[i][j] = matrice[i-curval][j-1];  //Je peux faire n avec m si dans la matrice à la case [n-m][n-1] il y a true

               }
           }
       }

        /* Calcul de l'enumeration des sommes*/
        for(int i=0; i<=somme; i++){
            calculer_enumeration(matrice,i, new Somme(multiEnsemble.size(), i), multiEnsemble.size()-1);
        }
    }

     /**
      * Affichage de la matrice
      */
    public void affiche_matrice(){

        System.out.print("   ");
        for(int i = 0 ; i <= somme ; i++){
            System.out.printf("%3d",i);
        }
        System.out.println();
        for(int i = 0  ; i < multiEnsemble.size() ; i++){
            System.out.printf("%3d",multiEnsemble.get(i));
            for(int j = 0 ; j <= somme ; j++){
                if(matrice[j][i])
                    System.out.printf("%3d",1);
                else
                    System.out.printf("%3d",0);
            }
            System.out.println();
        }
    }


    /**
     * This recursive method calculates for an integer "indice_somme", all the subsets of our multi-set that fit the sum, and stores it in "resultat"
     * @param matrice The Matrix we filled with True of False
     * @param indice_somme The sum we want to obtain
     * @param result The current state of our research, containing the elements we already added
     * @param indice_ensemble The line from which we start the recursive search
     */
    public void calculer_enumeration(boolean[][] matrice, int indice_somme, Somme result, int indice_ensemble){

        for(int i = indice_ensemble ; i >= 0 ; i--){

            if(matrice[indice_somme][indice_ensemble]){
                int res = indice_somme - multiEnsemble.get(i);
                if(res > 0){
                    result.add(i);
                    calculer_enumeration(matrice, res, result, i-1);
                    result.remove(i);
                }
                else if(res == 0){
                    result.add(i);
                    resultat.add(result.clone());
                    result.remove(i);
                }

            }

        }
    }

    /**
     *
     * @return The ArrayList of "Somme" representing our enumeration
     */
    public ArrayList<Somme> getResult(){
        return resultat;
    }


    public String toString(){
        String res = "";

        for(Somme s : resultat)
            res=res+s.toString();

        return res;
    }

}


